package com.leetcode.algorithm.y19.m03;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (TODO)96. 不同的二叉搜索树
 * (done)95. 不同的二叉搜索树 II
 * (done)530. 二叉搜索树的最小绝对差
 * @author: jie.deng
 * @time: 2019年3月27日 上午10:03:06
 */
public class MySolution0327 {
	
	/**
	 * 96. 不同的二叉搜索树
	 * 
     * 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
     * 
     * 示例:
     * 
     * 输入: 3
     * 输出: 5
     * 解释:
     * 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
     * 
     *    1         3     3      2      1
     *     \       /     /      / \      \
     *      3     2     1      1   3      2
     *     /     /       \                 \
     *    2     1         2                 3
	 * @param n
	 * @return
	 */
    public int numTrees(int n) {
		return n;
    }
    
    /**
     * 95. 不同的二叉搜索树 II
     * 
     * 给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
     * 
     * 示例:
     * 
     * 输入: 3
     * 输出:
     * [
     *   [1,null,3,2],
     *   [3,2,null,1],
     *   [3,1,null,null,2],
     *   [2,1,3],
     *   [1,null,2,null,3]
     * ]
     * 解释:
     * 以上的输出对应以下 5 种不同结构的二叉搜索树：
     * 
     *    1         3     3      2      1
     *     \       /     /      / \      \
     *      3     2     1      1   3      2
     *     /     /       \                 \
     *    2     1         2                 3
     * @param n
     * @return
     */
	public List<TreeNode> generateTrees(int n) {
//		思路： 
//		从小往大生成，新来一数，肯定比现有的节点都大 那么n可以成为现在所有树的父节点，并且他们都是n的左子树 
//		第二步就是沿着现有子树的右侧尝试不断插入。 如果插入以后，n还有子树，那么这些子树都是n的左子树。 
		List<TreeNode> preList = new ArrayList<TreeNode>();
		List<TreeNode> curList = new ArrayList<TreeNode>();
		int i = 1;
		while (i <= n) {
			if (i == 1) {
				curList.add(new TreeNode(i));
				i++;
				continue;
			}
			preList = curList;
			curList = new ArrayList<TreeNode>();
			for (TreeNode node : preList) {
				// 作为 [1,i-1]树的父结点
				TreeNode cur = new TreeNode(i);
				cur.left = cloneTree(node);
				curList.add(cur);

				//
				TreeNode cloneTree = new TreeNode(node.val);
				TreeNode cloneTreeR = cloneTree;	// cloneTree的最右孩子结点
				if (node.left != null) {
					cloneTree.left = cloneTree(node.left);
				}
				TreeNode right = node.right; // 用于标识node的右孩子结点[的右孩子结点]*
				while (right != null) {
					cur = cloneTree(cloneTree);
					// 
					TreeNode rr = cur;
					while (rr.right != null) {
						rr = rr.right;
					}
					rr.right = new TreeNode(i);
					rr.right.left = cloneTree(right);
					curList.add(cur);

					cloneTreeR.right = new TreeNode(right.val);
					cloneTreeR = cloneTreeR.right;
					if (right.left != null) {
						cloneTreeR.left = cloneTree(right.left);
					}

					right = right.right;
				}
				
				// 作为 [1,i-1]树的最右孩子结点
				cloneTreeR.right = new TreeNode(i);
				cur = cloneTree(cloneTree);
				curList.add(cur);
			}
			i++;
		}
		return curList;
	}
	
	private TreeNode cloneTree(TreeNode node) {
		TreeNode root = new TreeNode(node.val);
		if (node.left != null) {
			root.left = cloneTree(node.left);
		}
		if (node.right != null) {
			root.right = cloneTree(node.right);
		}
		return root;
	}

	/**
	 * 530. 二叉搜索树的最小绝对差
	 * 
     * 给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。
     * 
     * 示例 :
     * 
     * 输入:
     * 
     *    1
     *     \
     *      3
     *     /
     *    2
     * 
     * 输出:
     * 1
     * 
     * 解释:
     * 最小绝对差为1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
     * 注意: 树中至少有2个节点。
	 * @param root
	 * @return
	 */
	public int getMinimumDifference(TreeNode root) {
		// 思路:中序遍历，同时记录上次遍历过的结点，用于计算两节点的差
		TreeNode pre = null;
		TreeNode cur = root;
		int minDiff = Integer.MAX_VALUE;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		while (cur != null || !stack.isEmpty()) { // 划重点
			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}
			if (!stack.isEmpty()) {
				cur = stack.pop();
				if (pre != null) {
					int diff = cur.val - pre.val;
					if (diff < minDiff) {
						minDiff = diff;
					}
				}
				pre = cur;
				cur = cur.right;
			}
		}
		return minDiff;
	}
}
